Reusablility and Concurrency Issues in the Real-time Use of Ada*
This paper will present our explorative work in software reusability and concurrent programming. This work was divided into two parts. First, in order to abstract the reusable components, three application problems were tried to be solved by means of object-oriented programming using Ada. Second, in order to address how Ada provides an environment for concurrent programming, several concurrent programming concepts were described using Ada. ; Technical Report 2018-07-ECE-005 Technical Report 87-CSE-11 Reusability and Concurrency Issues in the Real-time Use of Ada* W. P. Yin P. H. Liou Murat M. Tanik This technical report is a reissue of a technical report issued May 1987 Department of Electrical and Computer Engineering University of Alabama at Birn1ingham July 2018 Technical Report 87-CSE-11 REUSABILITY ABD COBCURREIICY ISSUES IB THE REAL-TIME USE OF Ada• V. P. I:in P. B. Liou H. H. Tanik Department of Computer Science and Engineering Southern Methodist University Dallas, Texas 75275 May 1987 *Ada is a registered trade mark of the U.S. government, Ada Joint Program Office. Abstract REUSABILITY AND CONCURRENCY ISSUES IN THE REAL-TIME USE OF Ada* W. P. Yin P. H. Liou M. M. Tanik Department of Computer Science and Engineering Southern Methodist University Dallas, 'IX 75275 This paper will present our explorative work in software reusability and concurrent programming. This work was divided into two parts. First, in order to abstract the reusable components, three application problems were tried to be solved by means of object-oriented programming using A da. Second, in order to address how Ada provides an environment for concurrent programming, several concurrent programming concepts were described using Ada. 1. Introduction Reusability is a general engineering principle . It derives from the desire to avoid duplication and to capture commonality in undertaking classes of inherently similar works[ 1]. When software engineers try to apply this principle to software production, it brings many research questions into the open. The arguments focus on the question that what are the candidates for software reuse, how reusable software components should be stored, how we can locate reusable software components, and how we can incorporate reusable software components into our own software system. Concurrent Programming is the name given to programming notations and techniques for expressing paten tial parallelism and for solving the resulting synchronization and communication problems. Traditionally, the programs that run asynchronously were written in assembly language for the reasons : • High-level languages did not provide the appropriate tools for writing concurrent programs. • High-level languages for concurrent programming were not efficient. However, high-level language programs are easier to test, verify, and modify. Due to the progress on compiler techniques, we can obtain efficient object code for concurrent programs written in a high-level language. Concurrent programming is important because it provides an abstract setting in which studying parallelism becomes possible . The basic problem in writing a concurrent program is to identify the activities which are concurrent. It is also difficult to ensure the correctness of concurrent programs. In addition, concurrent programs are much more difficult to debug than sequential programs. * Ada is a registered trade mark of the U .8. government, Ada Joint Program Offi ce. - 2- Occasionally, asynchronous processes must interact with one another and these interactions can be complex. The following sections constitute a brief presentation of our explorative work for software reusability and concurrent programming using Ada. 2. Reusability Issue 2.1 Software Components and Their Reusability The term "; Computer Software" is used very often by most professionals and many members of the public at large . They feel they understand it. Most professionals have an intuitive feeling of it, but there is no complete and formal definition . Informally, computer software can be regarded as information having two basic formats: non-machine-executable and machine-executable[2]. Any information unit created by a software engineer during software development, such as specification, design, code, data and so on , is a software component. More abstractly, the problem solving knowledge, programming knowledge, problem domain knowledge and other knowledge which are used by software engineers in order to solve a problem by computer software are also software components. These knowledge assume specification, design, code and data as their external formats . Therefore, software reusability manifests itself in many forms . It can roughly be classified into reuse of data, reuse of code including programs, systems and libraries, reuse of programming knowledge including system architecture and detail design , reuse of domain knowledge including specification and reuse of abstract modules[3 ,4] . With respect to the time the reusable components are used , software reusability can be divided into two groups-reusability of components in building a variety of structures and reusability of components in performing a variety of tasks . Figure 1 depicts this idea. 2.2 Software Reusability Problems As a general engineering principle, reusability implies the obvious system benefits of lower cost, increased reliability and easier maintenance. It appears that the reusability principle should be used widely in software engineering. Unfortunately this is not true . According to some statistics, in commercial banking and insurance applications, about 75% of the functions were common ones that occurred in more than one program. There is also statistical data indicating that less than 15% of the code written in 1983 was unique, novel and specific to individual applications while the remaining 85% was more or less generic[3]. The main reason for the above situation is that regardless of the particular programming technique , design methodology or developing environment, software engineering is divided into individual creative processes. The exact nature of those individual process, such as problem identification, conceptual solution , design of implementation, testing of solution and so on , is poorly understood. Hence, reusing the software designed by other people is in general not a simple matter. Besides this , there are other reasons. First, some software is ";malevolent" because it is strongly self-centered and highly proprietary. That means it cannot be reused by organizations other than the developer. Second, even with "; benevolent" software, there are software engineers who may feel that they could produce a "; better" solution anyway. Third, some software may have to be modified excessively to fit the new application precisely. Fourth , some software may require a great effort to be understood in order to be reused. In the last two situations, software engineers would rather rewrite .[ 5] . - 3 - Figure 2 shows reusable component characteristics m terms of their functionality and scope. 2.3. Explorative Work in Software Reusability 2.3.1. The Problems In the following sections three problems are investigated. The problems are the environmental monitor problem[6], the cruise-control problem[7] and the message switching problem [8]. Those three are real-time problems. All of them require parallel processing, realtime control, exception handling and unique input/ output control. 2.3.2. The Method The ";object-oriented methodology" is chosen for solving the problems . Object-oriented methodology is a software approach in which the decomposition of a system is based upon the concept of objects. In real-time systems, often the problem is given by the description of entities, their behaviors and relations among the entities . In addition, object abstraction is a promising avenue for reusability. The object-oriented design methodology has the following steps [6, 7]: • Identify the objects and their attributes. • identify the operations. • Establish the visibility of each object in relation to other objects. • Establish the interface of each object. • Implement each object. 2.3.3. The Language Ada was chosen as the design language. Ada was chosen as a design language because of its rich variety of program units such as subprograms, packages and tasks . It is convenient for software engineers to choose one of the most suitable program units to represent classes of objects, instances of objects and primitive operations of each object. More importantly, the capabilities of Ada make it possible for us to break from the traditional flat, sequential design style into the object-centered design style. In particular, using Ada as a design language can improve the quality of the design by highlighting interfaces and formally capturing many important design decisions. 2.3.4. The Case Studies The case studies are concerned with the use of object-oriented design method for software reusability. The goal of the case-study was to explore how well the object-oriented method can apply the reusability principle. More specifically, how well the object-oriented method can recognize and abstract reusable software components for a specific class of problems (the real-time systems) . In this paper, the detailed case explanations will not be presented. Only are the observations and experiences listed. For each problem, first, a problem definition in problem space is given , then an informal system architecture design in conceptual solution space is presented . In the solution space , the details will be ignored; only objects and their operations are indicated. - 4- 2.3.4.1. Ca.se-1: Environmental Monitor Problem The environmental monitor problem is explained in detail in [6]. The figure 3 is the problem definition abstracted from [ 6] . And the figure 4 is the partial formalization of the system architecture design. Problem~ Objects and their Operations: ( 1) A user interacts with the system by setting the sensor limits, reading the status of all sensors , or q.u.it the system . ( 2) A printer Jlli,n.ts. the current reading of each sensor or s.h.u.t. rl.mYn. by the user. (3) Sensor r.e.ads. temperature or setting limit or s.h.u.t. d.mm. or initialized by user. ( 4) Monitor responds to out-of-limits sensor reading or detects the printer failure by setting an alarm. Also the alarm can be sh.n.t ~ Keeping the object-oriented methodology in mind, the transformation from the figure 3 to figure 4 is straightforward. In the step of identifying the objects and their attributes, the decision for specific representation of objects is delayed . We only take into account what objects in the problem space we are interested in . In general, the nouns denote the objects and the adjectives represent the attributes of each object. After identifying objects, extracting operations appropriate to each object is straightforward . The verbs attached to each object can be abstracted as corresponding operations . Those operations are visible outside. The object together with its operation forms one unit which can be defined by one program unit. The arrows are used to indicate the operation application direction . If there is one arrow from object A to object B, it indicates that the object A does one operation requiring something from B, or triggering B's operation . In this situation , the object A is an active object. If A is a passive object which does not have operations, all the arrows connected to A must point to A. System Specification in A.d.a package PRINTER is task THEYRINTER is entry PRINT_READING (THE_ITEM: in STRING); entry SHUT_DOWN; end THEYRINTER; end PRINTER; package ALARM is task THE_ALARM is entry REPOR T_OF LIMIT; entry REPORTYRINTER_ERROR; entry SHUT_DOWN; end THE_alarm; end ALARM; generic type NAME is ( ); type VALUE is range ; SENSE_RATE: in DURATION; - 5 - with function VALUE_OF (THE_NAME m NAME) return VALUE; with procedure SOUND_ALARM; package SENSORS is task type SENSOR is entry START (THE_NAME : in NAME) ; entry SET_LIMIT (THE_VALUE : in VALUE) ; entry GET_8TATUS (THE_VALUE : out VALUE; OUT_OF LIMITS : out BOOLEAN); entry SHUT_D OWN; end SENSOR; end SENSORS; type COMMAND is (SET_LIMIT, GET_8TATUS, SHUT_DOWN); procedure MONITOR is -- local type declarations -- ALARM task specification -- PRINTER task specification -- SENSOR task specification -- USER_COMMAND declaration -- task bodies begin -- manipulation of USER_COMMAND end MONITOR; Abstractions from ease-l: 1 Object-oriented design methodology is fundamentally different from traditional functional methods. Traditional functional methods factor system in problem space into operational modules in solution space , in which each operation module represents a major step in the overall transformation process. The object-oriented design method decomposes problem around objects that exist in the real world. 2 The object-oriented design method needs different requirement analysis to support. During the problem definition step, the requirement analyst must keep object orientedness in mind, because different analysis will get different problem decompositions. During the problem analysis , a good domain knowledge certainly helps a lot. 3 4 - 6 - It is necessary to use object-oriented system specification methodology during the system specification step. The specification is the result of a process of requirements analysis, and represents the first complete description of the conceptual solution. It contains clear descriptions of the external view of the system the user required along with any related or implied system constraints. The object-oriented system specification ideally closely matches the user's problem. It is desirable to make system specification consistent, completely, comprehensible and traceable to the requirement. Also , the object-oriented s specification will make the transaction between system specification and system design smooth, and easy. It is desirable to keep the system specification to be independent from the implementation . That means the transaction from problem space to conceptual solution space should not be restricted by implementations, especially not limited by the capability of implementation tools. Ada has the design description capability, but there is no direct notations for objects. 2.3.4.2. Ca.se-2: Cruise-Control System The Cruise-Control system problem is given in [7]. A data flow diagram (figure 5) is used to express the problem. This problem is more complicated than the environmental monitor system problem. The data flow diagram gives a clear view of each main step of the system transaction . Using object-oriented method the problem space is abstracted as in figure 6. From problem space the system architecture was abstracted using the object-oriented method (figure 7) . First, the objects and their operations are identified . Especially, the passive objects (no operations) and active objects (having operations) are distinguished; the required operations (triggered externally) and suffered operations (not triggered by outside world) are distinguished. For example, brake and accelerator are passive objects, others are active objects. Throttle has two v visible operations which are triggered by other objects and one invisible operation which is hiding in throttle's body. That invisible operation can only be seen by throttle itself. Problem~ Objects and their Operations: ( 1) Pulse from wheels: A pulse is. 5.f.D.t for every revolution of the wheel (2) Clock: Timing~ every milli-second. ( 3) Driver: If the driver s.fls. system on, it denotes that the cruise-control system should maintain the car speed. Also , the driver may require increasing or decreasing maintained speed when cruise-control on . Or, the driver requires resuming the last maintained speed. ( 4) Brake: If brake is. pressed, then cruise-control temporarily reverts to the manual control. ( 5) Brake state: Cruise-control requires the current brake state . ( 6) Engine state: If engine-on, the cruise-control may be active. (7) Accelerator: Accelerator state is. required by the cruise-control system. (8) Throttle: Setting the throttle value . Abstraction from case-2: - 7 - 1 An object is an entity that exists in time and space . An obje ct also has state . The operations indicate the object's state. Each object will be in one state at one time . The object state may change by the activity of other objects or as the time changes. We can trace the system activity in the state space . 2 We need facilities to indicate the time constraints of the system . For example, the clock's and wheel's operations must be synchronized. and the throttle has one operation-desired speed which can be visible by all the three operations of control increase, decrease and resume . 3 The ease-l and case-2 deal with different problems. The objects abstracted from these two problems are different, except one situation that the control object in cruise-control system is interacting with driver's requirement, the monitor object in environmental monitor system is interacting with user's command. Both system needs an interface with the user who will dynamically input his requirements / commands. This interface can be a reusable component. 2.3.4.3. Ca.se-3: Message Switching System The message switching problem is addressed in [8] . Figure 8 is the problem abstraction . The message switching system consists of a network of switching nodes connected via trunk lines. Each switching node is locally attached to subscribers , an operator, archive tape , and auxiliary memory. The operator can send and receive messages like any subscriber. In addition , the operator monitors and controls the node activity. The function of each node is to route input messages to one or more output destinations . Three successive phases are involved in processing each message: input, switch and output. inputReading input from a local subscriber or trunk link and storing the message on both auxiliary memory and an archive tape . switch Each input message contains a header, body and end marker. The header is examined to determine the output destination. For each destination , a directory is consulted to determine the appropriate output line to use and a copy of the message is queued for output on each distinct line. output A message is retrieved from auxiliary memory and written on the appropriate output line . Each message contains a priority as part of its header so that, at all times, the highest priority message for an output line is transmitted . If preempted, a message is later transmitted in its entirety. Having the experience of solving previous two problems, abstract objects and their operations can be obtained by repeatedly using the object-abstraction. Thus, we get the problem definition in object space (figure 9) and the concept solution (figure 10~. Pro b 1e m 8.p.a.c.e. Objects and their Operations: (1) Switches i.n.p.u.t message head and control signal. (2) Switches s.tu.r.e. the message on the auxiliary memory. (3) Switches archive message on the tape. . 8 . ( 4) Switches consult the cross-reference table to determine the appropriate output port. (5) Switches handle th e output message priority and preemption-output queue. (5) Switches output the message head and control signal to the output port. (7) Operator monitors the switch system . (8) Output ports retrieve the message body. This problem solution must solve the following four problems: • maximize I/ 0 parallelism , • control different I/0 devices, • coordinate mode activity, • handle output message preemptions. System Specification in A.d.a type MSG_A.DDR is STRING(l.20); type MSG is record HEAD : STRING(l.20); BODY: STRING(l.lOO); end record; task type ARCHIVE_TAPE is entry ARCHIVE (THE_NISG: in MSG); end ARCHIVE_TAPE; task type AUX_MEM is entry OUTPUT_NISG (THE_NISG_A.DDR in MSG_A.DDR); entry INPUT . MSG (THE_NISG_A.DDR : in MSG_A.DDR); end AUX_MEM; task type OUTPUT_CONTROL IS entry OUTPUT. . Jv1SG ( OUTPUT_pORT THE_NISG_A.DDR : in end OUTPUT_CONTROL; task type SWITCH is in STRING(1.20); MSG_A.DDR); entry INPUT_CONTROL (THE_NISG in MSG); end SWITCH; task type OPERA TORS is entry INPUT_MSG (THE_MSG m MSG); end OPERA TORS; task type SUBSCRIBER is entry INPUT.Jv1SG (THE_NISG in MSG); end SUBSCRIBER; OPERA TOR : OPERATORS; task body OPERA TOR is -- local type declarations -- ARCHIVE TAPE task declaration - g - -- AUXILIARY MEMORY task declaration -- OUTPUT CONTROL task declaration -- REFERENCE TABLE data structure declaration -- OUTPUT QUEUE data structure declaration THE.BUBSCRIBER : array ( 1.100) of SUBSCRIBER; task body THE.BUBSCRIBER is task OUTPUT_MSG; • • • end THE.BUBSCRIBER; THE.BWITCH : SWITCH; task body THE.BWITCH is procedure STORE_MSG (THE_MSG in MSG); procedure ARCHIVE_MSG (THE_MSG : in MSG); procedure CONSULT_TABLE (OUTPUT _FORT : out STRING( 1.10); THE_MSG : in MSG) ; procedure PREEMPTION (THE_MSG : in MSG; -- subprogram body • • • end THE.BWITCH ; -- other task bodies begin loop PRIORITY : out INTEGER); accept INPUT_MSG ( THE_MSG in MSG) do • • • end INPUT_MSG; end loop; end OPERATOR; - 10- Abstractions from case-3: 1 2 Using the object-oriented method to do system design really requires a great deal of real world knowledge and intuitive understanding of the problem, especially for abstracting operations. Listing the goal of the system requirements helps to decide which object should do which operation . For example, for this specific problem, the solution must solve the maximizing I / 0 parallelism and control different I/0 devices, it had better make auxiliary memory and archive-tape become active objects. The control issue and time constraint are important. It definitely needs some facilities to specify them . For example, the input-control for switch needs to specify its input trigger is exclusive OR, its output is sequential. In system architecture design using Ada, it seems that Ada's program units are not sufficient for this specification. 3 The three case studies come from different application fields. The software systems are required for different purposes. They deal with totally different objects. From the domain object level, it is not clear what is the reusable component. 2.3.5. Summary of Reusability Concepts 1 2 3 Software reusability is an attribute of software relative to its applicability in different computational contexts as well as different application areas. The object-oriented methodology is a better fit for real applications than other traditional methodologies. It is at least useful to apply reusability principle in the same application domain. Reusable software components tend to be objects or classes of objects. Given a rich set of reusable software components, the implementation would proceed via composition of these parts, rather than further decomposition. The greater abstraction of object models provides greater potential reusability. The level of abstraction has a great effect on reusability. Higher the abstraction, the greater overhead it may require for interpretation and it provides less intuitive understanding. Lower the abstraction, the chance of recognizing reusable components become less. 3. Concurrency Issues 3.1. Synchronization In a real time system, several processes may access the same data at the same time . This situation may result in inconsistent data. A language dealing with concurrent programming must guard against this possibility. That is, the language must provide the means to guard against time-dependent errors. When a process is accessing shared data, the process is said to be in its critical section ( or critical region). The concept of allowing only one process into its critical region at a time is known as mutual exclusion. An elegant software implementation of mutual exclusion was presented by Dekker. Dijkstra also abstracted the key notation of mutual exclusion in his concept of semaphores [10] . 3.1.1. Semaphores A semaphores is a protected integer variable which can take on only non-zero values and whose value can be accessed and altered only by the operations P(s), stands for wait, and V(s), stands for signal, and an initialization operation. Binary semaphores can accept only the - 11 - values 0 or 1. General semaphores can accept non-negative integer values . The definition of P and S is as follows : P(s): If s > 0 then s :=s- 1 else the execution of the process that called P(s) is suspended. V(s) :If some process P has been suspended by a previous P(s) on the semaphores then wake up P else s := s + 1 3.1.2. Monitors The above methods are so primitive that it is difficult to express solutions for more complex concurrency problems, and their presence in concurrent programs increases the existing difficulty of proving program correctness [ 12]. Another drawback of the above methods was that every procedure had to provide its own synchronization explicitly. A desire to provide the appropriate synchronization automatically led to the development of a new construct, a monitor [10]. A monitor is a concurrency construct that contains both the data and the procedures needed to perform allocation of a shared resource or group of shared resources. The monitor enforces information hiding - processes calling the monitor have no idea of, nor access to, data inside the monitor. Mutual exclusion is rigidly enforced at the monitor boundary- only one process at a time is allowed to enter. If a process inside the monitor cannot proceed until a certain condition becomes true, the process calls wait (variables name) and waits outside the monitor on a queue for ";variables name" to be signaled by another process. To ensure that a process already waiting for a resource eventually does get it, the monitor gives higher priority to a waiting process relative to a new requesting process attempting to enter the monitor. A process calling wait is threaded into the queue; a process calling signal causes a waiting process to be removed from the queue. 3.2. Ada Rendezvous Ada is a higher-level program mg language which can be used for conventional programming. In this section, we are concerned with the features of Ada related to concurrent programming. Central to these features is the concept of the task which is a program module that is executed asynchronously. Tasks may communicate and synchronize their actions through : 1 accept statement: It is a combination of procedure calls and message transfer. 2 select statement : It is a non-deterministic control structure based on guarded command construct. The BNF of them are : accept statement has the form : accept entry~imple_name [( entry_index)] [formal_part] do sequence_of~tatemen ts end [ entry~imple_name]; select statement has the form : select [when boolean_expression =>] - 12- acce p L.s tate men t seq ue n ce_of .s tatements {or [when boolean_expression =>] acce pt.s tatemen t} se qu ence_of.s tatemen ts [else se quence _of.s tatemen ts] end select; Following sections are Ada programs that implement the above mentioned concurrent problems. 3.2.1. Dekker's Algorithm procedure DEKKER is FAVOREDPROCESS : INTEGER; Pl WANTSTOENTER, P2WANTSTOENTER : BOOLEAN; procedure TWOYROC (PlWANTSTOENTER, P2WANTSTOENTER : in out BOOLEAN; FAVORED PROCESS : in out INTEGER) is task Pl; task body Pl is begin loop Pl WANTSTOENTER :=TRUE; while P2WANTSTOENTER loop if FAVOREDPROCESS = 2 then Pl W ANTSTOENTER := FALSE; while FAVOREDPROCESS = 2 loop null; busy waiting end loop; PlWANTSTOENTER :=TRUE; end if; -- you can enter critical region for Pl from here FAVOREDPROCESS := 2; PlWANTSTOENTER :=FALSE; -- you may put other s tuff here end loop; end loop; endPl; task P2; task body P2 is begin P2WANTSTOENTER :=TRUE; while Pl WANTS TO ENTER loop - 13 - ifF A VORED PROCESS = 1 then P2WANTSTOENTER := FALSE; while FAVORED PROCESS = 1 loop null; busy waiting end loop; P2WANTSTOENTER :=TRUE; end if; -- you may enter critical region for P2 form here FAVOREDPROCESS := 1; P2WANTSTOENTER :=FALSE; --you may put other stuff here end loop; end loop; endP2; begin null; -- main program for TWO_pROC end TWO_pROC; begin P1 W ANTSTOENTER := FALSE; P2WANTSTOENTER :=FALSE; FAVORED PROCESS := 1; TWO_pROC (P1wantstoenter, P2wantstoenter, favoredprocess) ; end DEKKER; 3.2.2. Semaphore (Binary) The following are two approaches of Binary Semaphore . The first one is described in [10] and the second one exactly follows the original definition of sem aphore. 3.2.2.1. procedure BINARY ,SEMAPHORE is ta.sk SEMAPHORE is entry P; entryV; end SEMAPHORE; ta.sk body SEMAPHORE is begin loop accept P; only after P has been called that V accept V; can be accepted and vice versa end loop; end SEMAPHORE; task Pl; task body P 1 is begin loop - 14- -- you may put the remainde r of the program one here SEMAPHORE.P; -- call the P entry -- now you can go ahe ad to access the critical region SEMAPHORE.V; -- call the V entry end loop; end Pl; task P2; task body P2 is begin loop -- you may put the remainder of the program one here SEMAPHORE.P; -- call the Pen try -- now you can go ahead to access the critical region SEMAPHORE.V; -- call the V entry end loop; end P2; begin -- main program for BINARY_8EMAPHORE null; end BINARY_8EMAPHORE; 3.2.2.2. According to the definition, semaphore is a protected variable whose value can be accessed and altered by operations P and V and initial operation. So, we declare semaphore as private type and only those subroutines inside this package can access its value package BIN_8EMAPHORE is type SEMAPHORE is private; procedure P (S: in out SEMAPHORE); procedure V (S: in out SEMAPHORE); procedure INITIAL_8EMAPHORE(S: in out SEMAPHORE; VALUE : in INTEGER); private type SEMAPHORE is record VAL : INTEGER; end record; end; package body BIN.SEMAPH ORE is NO_ WAITING :INTEGER := 0; - 15 - -- Il:um her of processes that have been suspended task CONTROL is entry SUSPEND ; entry W AKE_UP; end; task body CONTROL is begin loop accept WAKE_UP do accept SUSPEND; end; end loop; end CONTROL; procedure P (S : in out SEMAPHORE) is begin if S.VAL > 0 then S.VAL := S.VAL - 1; else NO_ WAITING := NO_WAITING + 1; CONTROL.SUSPEND; -- suspend the process end if; endP; procedure V (S : in out SEMAPHORE) is begin if NO_ WAITING > 0 then CONTROL.WAKE_UP; -- wakeup one of the suspended processes NO_WAITING := NO_WAITING- 1; else S.VAL := S.VAL + 1; end if; end V; procedure INITIAL.SEMAPHORE (S: in out SEMAPHORE; VALUE : in INTEGER) is begin S.V AL :=VALUE; end INITIAL_sEMAPH ORE; end BIN_sEMAPH ORE; - 16 - with BIN_sEMAPHORE; use BIN_sEMAPHORE; procedure SEMAPH ORE_EXAMPLE is S: SEMAPHORE; procedure TWOYROC is task PROCESSONE; task body PROCESSONE is begin loop -- put some stuff here P(S); -- now you are inside the critical region one V(S); -- put some other stuff here end loop; end PROCESSONE; task PROCESSTWO; task body PROCESSTWO is begin loop -- put some stuff here P(S); -- now you are inside the critical region two V(S); end loop; end PROCESSTWO; begin null; -- main program for two_proc end TWOYROC; begin -- main program for semaphore example INITIAL_sEMAPHORE(S, 1); TWOYROC; -- now, two processes are executing concurrently - 17 - end SEMAPH ORE_EXAMPLE; 3.2.3. Binary Semaphore Using Monitor Concept In the following example we describe the implementation of a binary semaphore by a monitor written in Ada. generic package GENERIC_MONITOR is task type COND PTR is entry WAIT; entry SIGNAL; end COND PTR; type CONDITION is access COND PTR; -- This condition type of variab le provides a queue for wait entry, also for the signal entry. end GENERIC_MONITOR; package body GENERIC_MONITOR is task body COND PTR is begin loop accept SIGNAL do accept WAIT; end; end loop; end CONDPTR; end GENERIC_MONITOR; with GENERIC_MONITOR; procedure SEMAPHORE_USE_MONITOR is This package(monitor) performs information hiding. Procedures calling the monitor have no idea of, nor access to, data inside the monitor. package MONITOR is procedure P; procedure V; end MONITOR; package body MONITOR is - 18- package TEMP is new GENERIC_MONITOR; use TEMP; NOT_BUSY : CONDITION; BUSY: BOOLEAN := FALSE; procedure P is begin if BUSY then NOT_BUSY.WAIT; -- wait entry provides a queue for the -- procedures waiting to be accepted end if; BUSY :=TRUE; endP; procedure V is begin BUSY := FALSE; NOT_BUSY.SIGNAL; -- wake up the procedure at the first -- on the queue of wait entry endV; end MONITOR; use MONITOR; procedure TWOYROC is task P1 ; task body P1 is begin loop P; -- you can enter the critical region 1 now V ; -- you may put the rest of the stuff here end loop; endP1; task P2; task body P2 is begin loop P; -- you can enter the critical region 2 now V; -- you may put the rest of the stuff here end loop; end P2 ; - 1 g - begin -- main program of two_proc null; now Pl and P2 are executing concurrently end TWOYROC; begin -- main program of SEMAPHORE_USE_MONITOR TWO_?ROC; end SEMAPHORE_USE_MONITOR; 3.3. Real-Time Interrupt Handling Efficient interrupt handling is critical in real-time environments. Interrupts are used to control the transfer of data to and from external devices, which often generate interrupts at high frequencies. If the interrupt is not handled quickly, external data can be lost or overall efficiency of the system can be severely degraded . Real-time performance requirements are determined by the minimum time between arrival of interrupts and the maximum time that can elapse while an interrupt is pending before data are lost or a hardware time-out occurs. When an interrupt occurs, a processor must begin executing code in another environment. Context switching is machine dependent, and in most modern computers it is supported by special privileged instructions. Interrupt handling takes at least two context switches, one from the program currently running to the interrupt handler and one at the completion of the interrupt handler. However, neither of these need to be full context switches, nor do interrupts need to be disabled for long. 3.3.1. Language Mechanisms for Interrupt Handlers in Ada Most real-time software for embedded systems use interrupt handlers to control and communicate with external devices . Interrupt handlers are usually responsible for initializing devices, initiating physical I/0 operations and responding to both anticipated and unanticipated interrupts. Ideally, interrupts would arrive only as a direct consequence of a previously issued software command. However, in practice, interrupts can arrive unexpectedly or fail to arrive when expected. Interrupt handlers have traditionally been written in assembly language because few high-level languages provide support for interrupts and because interrupt handlers must often meet severe real-time constraints [15] . Mechanisms for implementing interrupt handlers provided by systems programming languages such as Concurrent Pascal and Modubv-2 are usually not optimized for real-time applications. Since Ada was intended for embedded applications, interrupt-handling mechanisms were integrated into Ada. The Ada Language Reference Manual (LRM) [18] briefly describes interrupt handlers and their semantics (in sec. 13.7) . The following example from the LRM illustrates the specification of an interrupt handler: t.a.sk INTERRUPT_HAND LER is entry DONE; for DONE use at 16#40#; end INTERRUPT_HANDLER; - 20- The task specification n, or interface, de fines each externally visible task operation , referred to as an entry. The semantics of an interrupt is defined in terms of the rendezvous which was dis- [ cussed in previous sections. Each Ada process, or task, declares a list of entry procedures that can be called by other tasks. A rendezvous occurs between a calling task and the serving task when the caller is waiting to execute an entry call, and the server is waiting to accept the en try call. Each task specification must have a corresponding body that contains the executable code of the task. The following is a more realistic example of an interrupt handler for a printer device [ which illustrates some of the hardware and software run-time support actions that must be considered when programming interrupt handlers. task PRINTER_8ERVER is entry OUTPUT__LINE (ST : in STRING); entry IO_INTERRUPT; for IO_INrERRUPT use at 16#1234#; end PRINTER_8ERVER; task body PRINTER_8ERVER is HARDWAREYORT : CHARACTER; for HARDWAREYORT use at 16#1234#; begin loop accept OUTPUT__LINE (ST : in STRING) do for INDEX in ST'RANGE loop HARDWAREYORT := ST(INDEX); accept IO_INTERRUPT; end loop end OUTPUT__LINE; HARDWAREYORT := ASCII.CR; accept IO_INTERRUPT do HARDWAREYORT := ASCII.LF; end IO_lNTERRUPT; accept IO_INTERRUPT; end loop; end PRINTER_8ERVER; The above example illustrates how it is possible in Ada to serve the same interrupt entry point with different accept bodies. 3.3.2. Interrupt Handling Model in Ada Hardware interrupts generated by a device or its controller are usually described informally by means of flowcharts and timing diagrams, in contrast to software whose behaviour is defined by a program . A uniform description of both the hardware and software makes it possible to define a model for a general-purpose , interrupt-handling mechanism [17]. The complete chain of control from the hardware to the server can be modeled by three Ada tasks , where the first two are asynchronous tasks external to the server. The first task - 21 - represents a hardware device, which is a producer of interrupts and a producer or consumer of data. The second task represents the hardware /software interface , and performs interrupt enabling , disabling and context switching outside the normal Ada rendezvous mechanisms. The task specifications are as follows: HARDWARE_DATA : DEVICE_DEPENDENT; task ASYNCHRONOUS_HARDWARE; task INTERFACE is entry D ISPA TCHJNTERRUPT; end INTERFACE; task SERVER is entry OUTPUT_LINE (ST: in STRING) ; entry IOJNTERRUPT; for IOJNTERRUPT use at 16#1234#; end SERVER; The advantage of adopting an Ada model for devices and their run-time support is that the semantics of interrupt handling can be defined entirely in Ada. This model can be used conveniently to illustrate some of the problems an effective implementation must be able to handle : 1. hardware that generates interrupts at power-up and in error situations where there is no Ada program or handler ready to serve interrupts 2. hardware that generates spurious interrupts when the interrupt handlers are not ready to serve interrupts 3. hardware that requires immediate action on the interrupt to prevent the loss of data 4. a hardware interrupt that demands a specific program action to mask it out so that it is not constantly pending. 3.3.2.1. The Hardware/Software Interface The interface is modeled by a task representing the connection between the hardware and server tasks that are running concurrently on two conceptually different processors with a need to communicate. The hardware task has no knowledge of the state of the software and can try to interact with it at unexpected times. Some hardware tasks must be serviced immediately, even if the server is not ready, and can therefore generate unexpected interrupts (and race conditions in the server) when interrupt handlers are too slow to handle successive interrupts. A model for robust and usable interrupt support environment must provide services for situations in which either software or hardware is malfunctioning. This kind of failure handling can be represented by the following body of the interface task . task body INTERFACE is begin loop - 22- accept DISPATCHJNTERRUPT do select-- conditional en try call SERVER.IOJNTERRUPT; else FAIL URE_8ERVER.SERVER_NOT_READ Y; end select; end DISPATCHJNTERRUPT; end loop; end INTERFACE; 3.3.2.2. The Hardware Task The Ada hardware task example below models many of the problems caused by actual hardware . In the ex ample , the server and interface tasks communicate with the hardware task v1a a global HARDWARE_DATA variable, which includes the fields INTERRUPT_ENABLED , STARTJO and IO_DA TA. task body ASYNCHRONOUS_HARD WARE is -- lo cal declarations procedure GENERATEJNTERRUPT(TIMEOUT NATURAL) is begin PENDING JNTERR UPT: for I in O . TIMEOUT loop if HARDWARE_DATA.INTERRUPT_ENABLED then select -- conditional en try call INTERF A CE.D ISPA TCHJNTERRUPT; ifDATA_UNSTABLE then HARDWARE_DATA.IO_DATA := IND ETERMINANT; end if; exit PENDINGJNTERRUPT; else if DATA_UNSTABLE then HARDWARE_DATA.IO_DATA end if; end select; end if; end loop PENDINGJNTERRUPT; end GENERA TEJNTERRUPT; begin loop IND ETERMINANT; SERVICEJNTERVAL := SERVICEJNTERV AL + 1; if SERVICEJNTERVAL > SERVICE_TIMEOUT then GENERATEJNTERRUPT (INTERRUPT_TIMEOUT) ; SERVICEJNTERVAL := 0; end if; if HARDWARE_DATA.STARTJO then - 23- for I in O . DO_IO_TIME loop null; end loop; HARD WARE.J) ATA.IO_DA TA :=VALID _DATA; GENERA TE_INTERRUPT ( IO_D ONE_TIMEOUT); end if; end loop; end ASYNCHRONOUS.JIARD WARE; The hardware and interface model is sufficiently general to cover a wide range of hardware devices and enables a specification of requirements for designing a system hardware support package. Without such a formal definition, it is difficult to verify the correctness of the interrupt run-time support package. In addition, the model permits a software task to simulate a hardware device and test the interrupt run-time support package. 3.4. Conclusion The traditional approach to implementing interrupt handlers using assembly language le ads to systems that are difficult to develop, maintain or adapt to new hardware and software requirements. By providing a high-level interface, Ada simplifies the design and maintenance of interrupt handlers . And Ada defines the semantics of tasking mechanism, making it possible to construct asynchronous and synchronous programming models. Ada not only provides a powerful tool from software resuability point of view but also provides a powerful tools for concurrent programming. It really is "; The Language for the 1980s ";(May be 1990s). References [1] P.Wegner ";Capital-Intensive Software Technology,"; IEEE Software, Vol. 1, No.3, July, 1984, p. 3-45. [2] R. S. Pressman, Software Engineering, McGRAW-HILL, Inc. 1987, p. 5-8. [3] T . C. Jones , ";Reusability In Programming: A Survey of the State of the Art,"; IEEE Trans. Software Eng., Vol. SE-10, No.5, sept. 1984, p. 488-497. [ 4] G. Jones, ";Software Reusability: Approaches and Issues,"; Pro c. of IEEE computer Software f3 Applications Gonf., Nov. 1984, p. 476-477 . [ 5] M. D . Lubars, ";Code Reusability in the Large vs . in the Small,"; AG!vf SIGSOFT Software Engineering Notes, Vol. 11, No.1, Jan. 1986, p. 21-27. [6] G . Booch, Software Engineering With Ada, The Benjamin/Cummings Publishing Company, Inc., 1987, p. 334-354. [7] G. Booch, "; Object-Oriented Development,"; IEEE Trans. software Eng., Vol. SE-12, No. 2, Feb. 1986, p. 211-221. [8] G . R. Andrews, ";The Design of a Message Switching System : An Application and Evaluation of Modula,"; IEEE Trans. Software Eng., Vol. SE-5, No.2, Mar. 1979, p. 138- 147. [9] J. G . P. Barnes, Programming in Ada, Addison-Wesley, 1984. - 24- [10] M. Ben-Ari, Principles of Concurrent Programming, Prentice-Hall International, 1983. [11] G. Booch , Software Engineering with Ada, Benhamin/Cummings, 1983. [ 12] H. M. D eitel, An Introduction to Operating System, Addison-Wesley, 1983. r [13] J. Peterson and A. Silberschatz, Operating System Concepts, Addison-Wesley, 1983 . [ 14] M. M. Tanik, ";A Comparative Study of Synchronization Models Exploitable for Real [ Time Software Development Environment Design and Testing", SMU Technical Report 87-CSE-1, 1987. M. M. Tanik, ";Message Based Kernel in Communications", AACI Tech . Report, 1984. ( [ 16] ";Analyzing Ada Concurrent Programming", ACM Ada LETTERS, March-April, 1987. [ 17] J. B. Rasmussen and B. Appelbe, ";Real-time Interrupt Handling in Ada", Software Practice and Experience, Vol. 17, No. 3, Mar. 1987, p.197-213. [18] United States Department of Defense, Reference Manual for the Ada Programming Language, ANSI/MIL-STD 1815A, Feb. 1983.